#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>

template <typename T>
class StackNode
{
public:
  T _data;
  StackNode<T> *_next;

  StackNode():_next(nullptr) { }
  StackNode(T data): _data(data), _next(nullptr) { }
  StackNode(T data, StackNode<T> *next): _data(data), _next(next) { }
};

template <typename T>
class LinkStack
{
private:
  uint16_t _capacity;
  uint16_t _size;
  StackNode<T> *_first;

public:

  LinkStack(): _capacity(5), _size(0), _first(nullptr)
  {
    printf("LinkStack()\n");
  }

  LinkStack(uint16_t capacity): _capacity(capacity), _size(0), _first(nullptr)
  {
    printf("LinkStack()\n");
  }

  ~LinkStack()
  {
    while (_first != nullptr) {
      StackNode<T> *temp = _first->_next;
      delete _first;
      _first = temp;
    }
    printf("~LinkStack()\n");
  }

  uint16_t Size() {
    return _size;
  }

  uint16_t Capacity() {
    return _capacity;
  }

  bool Empty() {
    return _first == nullptr;
  }

  bool Full() {
    return _size == _capacity;
  }

  bool Push(T data) {
    if (Full()) {
      fprintf(stderr, "ERROR: link stack is full.\n");
      return false;
    }
    StackNode<T> *temp = new StackNode<T>(data);
    temp->_next = _first;
    _first = temp;
    _size++;
    return true;
  }

  T Pop() {
    if (Empty()) {
      fprintf(stderr, "ERROR: link stack is empty.\n");
      exit(-1);
    }
    T ret = _first->_data;
    _first = _first->_next;
    _size--;
    return ret;
  }

  T Top() {
    if (Empty()) {
      fprintf(stderr, "ERROR: link stack is empty.\n");
      exit(-1);
    }
    return _first->_data;
  }

};


int main()
{
  LinkStack<int> stack;
  printf("capacity: %u, size: %u\n", stack.Capacity(), stack.Size());
  stack.Push(10); printf("Peek: %d\n", stack.Top());
  stack.Push(20); printf("Peek: %d\n", stack.Top());
  stack.Push(30); printf("Peek: %d\n", stack.Top());
  stack.Push(40); printf("Peek: %d\n", stack.Top());
  stack.Push(50); printf("Peek: %d\n", stack.Top());
  printf("capacity: %u, size: %u\n", stack.Capacity(), stack.Size());
  stack.Push(60);

  printf("Pop: %d\n", stack.Pop());
  printf("capacity: %u, size: %u\n", stack.Capacity(), stack.Size());

  return 0;
}

